685E - Travelling Through the Snow Queen's Kingdom - CodeForces Solution

# include <cstdio>
# include <algorithm>
# include <cmath>
# include <iostream>
# include <cstring>
# include <vector>
# include <queue>
using namespace std;
const int MAXN = 1e3 + 10, MAXM = 2e5 + 10;
int e[MAXM][2], f[MAXN][MAXN], n, m, q;
bool ans[MAXM];
struct query {
	int l, r, s, t, id;
}que[MAXM];
bool cmp(query A, query B) {
	return A.r < B.r;
}
void SOLVE() {
	cin >> n >> m >> q;
	for (int i = 1; i <= m; i++) {
		cin >> e[i][0] >> e[i][1];
	}
	for (int i = 1; i <= q; i++) {
		cin >> que[i].l >> que[i].r >> que[i].s >> que[i].t;
		que[i].id = i;
	}
	sort(que + 1, que + q + 1, cmp);
	int t = 1;
	for (int i = 1; i <= m; i++) {
		int u = e[i][0], v = e[i][1];
		f[u][u] = f[v][v] = i;
		for (int j = 1; j <= n; j++) f[j][u] = f[j][v] = max(f[j][u], f[j][v]);
		while (t <= q && que[t].r <= i) {
			ans[que[t].id] = f[que[t].s][que[t].t] >= que[t].l;
			t++;
		}
	}
	for (int i = 1; i <= q; i++) {
		cout << (ans[i] ? "Yes" : "No") << "\n" ;
	}
}

int main() {
	//freopen("1.in", "r", stdin);
	ios::sync_with_stdio(false);
	cin.tie(0);
	long long T = 1;
	while (T--) SOLVE();
	return 0;
}